递归和动态规划——最长公共子序列

例：
str1 = “1A2C3D4B56“;
str2 = “B1D23CA45B6A”
则最长公共子序列为”12C4B6”。

实现：动态规划（注意公共子序列中的每个字符可能不连续）
步骤一：str1的长度为M，str2的长度为N，生成大小为M*N的矩阵dp，dp[i][j]表示使用str[0,…i]与str[0,…j]的最长公共子序列的长度。

1. dp第一列dp[0,..M-1][0]表示str1[0,…M-1]与str2[0]的最长公共子序列的长度。str2[0]只有一个字符，dp[i][0]的最大值为1，如果str1[i]==str2[0]，则dp[i][0]=1，dp[i+1,..M-1][0]也为1.
2. dp第一行dp[0][0,..N-1]与步骤1dp第一列同理。如果str1[0]==str2[j]，则令dp[0][j]=1,dp[0][j+1,…N-1]也为1。
3. 对非第一行第一列，dp[i][j]可能来自下面3种情况：
   1）dp[i-1][j]（类比第一列）
   2）dp[i][j-1]（类比第一行）
   3）如果str1[i]==str2[j]，还可能是dp[i-1][j-1]+1（即来自左上角）。比如str1=”ABCE”，str2=”ABCE”

因此最长公共子序列为：
dp[i][j]=max{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1}

dp矩阵的右下角的值代表最长公共子序列的长度。

步骤二：获取具体的最长公共子序列

1. 从矩阵的右下角开始向上、向左或向左上移动，同时用字符数组char[] rst表示最长公共子序列。
2. 如果dp[i][j]大于dp[i][j-1]和dp[i-1][j]，说明在计算dp[i][j]时，一定来自决策dp[i-1][j-1]+1，可以确定str1[i]=str2[j],并且这个字符一定属于最长公共子序列，把这个字符放进字符数组rst中，然后向左上方移动。
3. 如果dp[i][j]=dp[i-1][j]，可以向上方移动
4. 如果dp[i][j]=dp[i][j-1]，可以向左方移动
5. 如果dp[i][j]同时等于dp[i-1][j]或dp[i][-1]，向上或向左都可以移动。

/*
 * 输出两个字符串的最长公共子序列，总时间复杂度为O(M*N)，
 * 额外空间复杂度（即使用dp动态规划表的复杂度）为O(M*N)。
 */
public class LongComSeq {
	/**
	 * 第一步：输出两个字符传的最长公共子序列矩阵
	 * 计算动态规划表dp中的位置，只是简单比较3个位置的值，复杂度为O(1)，
	 * 矩阵dp的大小为M*N，所以计算dp矩阵的时间复杂度为O(M*N)。
	 * @param str1 存第一个字符串的字符数组
	 * @param str2 存第二个字符串的字符数组
	 * @return str1[0,...i]和str2[0,...j]的最长公共子序列的长度
	 */
	public int[][] longComDq(char[] str1, char[] str2) {
		int[][] dp = new int[str1.length][str2.length];
		dp[0][0] = str1[0] == str2[0] ? 1 : 0; //(0,0)位置特殊处理
		for (int i = 1; i < str1.length; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
			/*if (str1[i]==str2[0]) {
				dp[i][0] = 1;
			}
			dp[i][0] = max{dp[i-1][0], dp[i][0]};
			*/		
		}
		for (int j = 1; j < str2.length; j++) {
			dp[0][j] = Math.max(dp[0][j - 1], str1[0] == str2[j] ? 1 : 0);
		}
		for (int i = 1; i < str1.length; i++) {
			for (int j = 1; j <str2.length; j++) {
				//非第一行第一列dp[i][j]的三种情况，可能来自上方，左方，左上方。
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				if (str1[i] == str2[j]) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				}
			}
		}
		return dp;
	}
	/**
	 * 第二步：根据动态规划表dp，输出最长公共子序列
	 * 通过dp得到最长公共子序列，向上最多移动M个位置，向左最多移动N个位置，
	 * 所以通过dp得到最长公共子序列的时间复杂度为O(M+N)。
	 * @param str1 原字符串str1 
	 * @param str2 原字符串str2
	 * @return str1[0,...i]和str2[0,...j]的最长公共子序列
	 */
	public String longComSeq(String str1, String str2) {
		//判断两个字符串引用是否为空（即是否有对象），如果有对象，判断对象是否为空字符串
		if (str1 == null || str2 == null || str1.equals("") || str2.equals("")){
			return ""; //返回空字符串
		}
		char[] cha1 = str1.toCharArray();
		char[] cha2 = str2.toCharArray();
		int[][] dp = longComDq(cha1, cha2); //生成动态规划表
		int m = cha1.length - 1; //索引从0到cha1.length - 1
		int n = cha2.length - 1;
		char[] rst = new char[dp[m][n]]; //dp动态规划表的右下角dp[m][n]为最长公共子序列的长度
		int index = rst.length - 1; //rst数组的尾索引，即dp[m][n]-1
		while (index >= 0) { //还原求解dp某条路径的过程
			if (m > 0 && dp[m][n] == dp[m - 1][n]) { //与上方相同，向上方移动
				m--;
			} else if (n > 0 && dp[m][n] == dp[m][n - 1]){ //与左边相同，向左方移动
				n--;
			} else { //dp[i][j]大于dp[i-1][j]和dp[i][j-1],与上方和左边都不同，则决策移动来自dp[i-1][j-1]+1
				rst[index--] = cha1[m]; //或cha2[n]（将String1或String2的字符放入）
				m--;
				n--;
			}
		}
		return String.valueOf(rst); //char[] -> String
	}

注意char类型数组转字符串String.valueOf(char[] chas)。ps:String真的是个“万能”类型！

	//Test
	public static void main(String[] args) {
		String str1 = "1A2C3D4B56";
		String str2 = "B1D23CA45B6A";
		String str3 = "ABCD";
		String str4 = "ABCD";
		char[] cha1 = str1.toCharArray();
		char[] cha2 = str2.toCharArray();
		LongComSeq lcs = new LongComSeq();
		int[][] dp = lcs.longComDq(cha1, cha2);
		System.out.println("由str1和str2组成的动态规划表dp:");
		for (int i = 0; i < dp.length; i++) {
			for(int j = 0; j < dp[0].length; j++) {
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("str1和str2的最长公共子序列为：");
		System.out.println(lcs.longComSeq(str1, str2));
		System.out.println();	
		char[] cha3 = str3.toCharArray();
		char[] cha4 = str4.toCharArray();
		LongComSeq lcs1 = new LongComSeq();
		int[][] dp1 = lcs1.longComDq(cha3, cha4);
		System.out.println("由str3和str4组成的动态规划表dp1:");
		for (int i = 0; i < dp1.length; i++) {
			for(int j = 0; j < dp1[0].length; j++) {
				System.out.print(dp1[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("str3和str4的最长公共子序列为：");
		System.out.println(lcs1.longComSeq(str3, str4));
	}
}

输出：

由str1和str2组成的动态规划表dp:
0 1 1 1 1 1 1 1 1 1 1 1 
0 1 1 1 1 1 2 2 2 2 2 2 
0 1 1 2 2 2 2 2 2 2 2 2 
0 1 1 2 2 3 3 3 3 3 3 3 
0 1 1 2 3 3 3 3 3 3 3 3 
0 1 2 2 3 3 3 3 3 3 3 3 
0 1 2 2 3 3 3 4 4 4 4 4 
1 1 2 2 3 3 3 4 4 5 5 5 
1 1 2 2 3 3 3 4 5 5 5 5 
1 1 2 2 3 3 3 4 5 5 6 6 
str1和str2的最长公共子序列为：
12C4B6

由str3和str4组成的动态规划表dp1:
1 1 1 1 
1 2 2 2 
1 2 3 3 
1 2 3 4 
str3和str4的最长公共子序列为：
ABCD